import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;


public class Ex3_5 {	
	
	private final String[] BASES = {"A","T","C","G"}; 
	
	public Ex3_5() {}	
	public static void main(String[] args) {
		
		Ex3_5 exe = new Ex3_5();
		ArrayList<String> dnas = exe.getDNAs("C:\\Users\\josemfer\\Downloads\\DNAs.txt");
		Integer k= 12;
		ArrayList<String>  res = exe.greedyMotifSearch(dnas, k);
		
		for (String r : res) {
			System.out.println(r);
		}	
		
		
	}
	
	
	/*
	 * GREEDYMOTIFSEARCH(Dna, k,t)
        form a set of k-mers BestMotifs by selecting 1st k-mers in each string from Dna
        for each k-mer Motif in the 1st string from Dna
            Motif1 <- Motif
            for i = 2 to t
                form Profile from motifs Motif1, …, Motifi - 1
                Motif_i ← Profile-most probable k-mer in the i-th string in Dna
            Motifs <- (Motif1, …, Motift)
            if Score(Motifs) < Score(BestMotifs)
                BestMotifs<- Motifs
        output BestMotifs
	 *	
	 */
	private ArrayList<String> greedyMotifSearch(ArrayList<String> dnas, Integer k) {
		HashMap<ArrayList<String>,Integer> scores = new HashMap<ArrayList<String>,Integer>();
		ArrayList<String> bestMotifs = new ArrayList<String>();
		Integer t = dnas.size();
		//form a set of k-mers BestMotifs by selecting 1st k-mers in each string from Dna
		for (String dna : dnas) {
			bestMotifs.add(dna.substring(0,k));
		}
		
		for (int i=0;i<=dnas.get(0).length()-k;i++) {
			String kmerFirstDna = dnas.get(0).substring(i,i+k);
			ArrayList<String> motifs = new ArrayList<String>();
			motifs.add(kmerFirstDna);	
			
			for (int j=1;j<t;j++) {
				HashMap<String,ArrayList<Double>> profile = genProfile(motifs);
				String kmer = getMostProbKmer(dnas.get(j), k, profile);
				motifs.add(kmer);
			}
			Integer sc = getScore(motifs) ;
			scores.put(motifs, sc);
			
			if (getScore(motifs) < getScore(bestMotifs)) {
				bestMotifs = motifs;
			}			
		}
		
		return bestMotifs;
		
	}
	
		
	private ArrayList<String> getDNAs(String file) {		
		ArrayList<String> lineas = new ArrayList<String>();		
		try {
			BufferedReader br = new BufferedReader(new FileReader(file));
			String line;
			while ((line = br.readLine()) != null) {
				lineas.add(line);
			}
			br.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
		return lineas;		
	}
	
	
	private HashMap<String, ArrayList<Double>> 
										genProfile(ArrayList<String> motifs) {
		HashMap<String, ArrayList<Double>> profile = 
									new HashMap<String, ArrayList<Double>>();
		Integer t = motifs.size();
		for (String base : BASES) {			
			// init base profile
			ArrayList<Double> baseProfile = new ArrayList<Double>();
			for (int i=0;i<motifs.get(0).length();i++) {
				baseProfile.add(1.0 / 2*t ); // Laplace pseudocounts
			}
			profile.put(base, baseProfile);		
			// iterate motifs
			for (String motif : motifs) {
				for (int i=0;i<motif.length();i++) {
					if (String.valueOf(motif.charAt(i)).equals(base)) {						
						baseProfile = profile.get(base);
						Double actual = baseProfile.get(i);
						Double newP = actual + (1.0/(2*t)); // Laplace pseudocounts
						baseProfile.set(i, newP);						
					}
				}				
			}
		}
		
		return profile;
	}
	
	private String getMostProbKmer(
					String dna, Integer k, HashMap<String, ArrayList<Double>> profile) {
		String finalKmer = null;
		Double probIni = 0.0;
		// If multiple kmers have same probability, get FIRST.
		// trick: read reverse string		
		for (int i=dna.length()-k;i>=0;i--) {
			String kmer = dna.substring(i,i+k);
			Double prob =  calculateProb(kmer,profile);
			if (prob >= probIni) {
				probIni = prob;
				finalKmer = kmer;
			}			
		}		
		return finalKmer;
	}
	
	private Double calculateProb(String kmer, 
							HashMap<String, ArrayList<Double>> profile ) {
		Double prob = 1.0;
		for (int i=0;i<kmer.length();i++) {
			String base = String.valueOf(kmer.charAt(i));
			prob = prob * profile.get(base).get(i);
		}		
		return prob;		
	}
		
	
	private Integer getScore(ArrayList<String> motifs) {
		Integer finalScore = 0;
		// create matrix of positions
		// HashMap:  <positions, list of bases >
		HashMap<Integer,ArrayList<String>> matrix 
						= new HashMap<Integer,ArrayList<String>>();
		for (String motif : motifs) {
			for (int i=0;i<motif.length();i++) {
				ArrayList<String> colum = matrix.get(i);
				if ( colum == null) {
					 colum = new ArrayList<String>();		
					 matrix.put(i, colum);
				} 
				colum.add(String.valueOf(motif.charAt(i)));				
			}
		}
		// calculate score using matrix
		Integer t = motifs.size();
		for (Integer position : matrix.keySet()) {
			HashMap<String,Integer> baseCounter = new HashMap<String,Integer>();
			// walking down rows...
			ArrayList<String> columBases = matrix.get(position);
			for (String base : columBases) {
				Integer baseCount = baseCounter.get(base);
				if (baseCount == null) {
					baseCount = new Integer(0);					
				}
				baseCount++;				
				baseCounter.put(base, baseCount);
			}
			// most frequent base in baseCounter?
			Entry<String,Integer> maxEntry = null;
			for(Entry<String,Integer> entry : baseCounter.entrySet()) {
			    if (maxEntry == null || entry.getValue() > maxEntry.getValue()) {
			        maxEntry = entry;
			    }
			}
			if ((maxEntry.getValue()) == 1) {
				finalScore += t;
			} else {
				finalScore += (t - maxEntry.getValue());
			}
		}
		
		return finalScore;
	}
		

}
